package com.algorithm.liyc.combine;

import java.util.*;

/**
 * 0332.重新安排行程
 * 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
 * 提示：
 *
 * ● 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
 * ● 所有的机场都用三个大写字母表示（机场代码）。
 * ● 假定所有机票至少存在一种合理的行程。
 * ● 所有的机票必须都用一次 且 只能用一次。
 *
 * @author Liyc
 * @date 2024/1/23 15:49
 **/

public class Solution13 {
    private Deque<String> result;
    private Map<String, Map<String, Integer>> map;
    public List<String> findItinerary1(List<List<String>> tickets) {
        result = new LinkedList<>();
        map = new HashMap<>();

        for (List<String> list : tickets) {
            Map<String, Integer> temp;
            if (map.containsKey(list.get(0))) {
                temp = map.get(list.get(0));
                temp.put(list.get(1), temp.getOrDefault(list.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(list.get(1), 1);
            }
            map.put(list.get(0), temp);
        }

        result.add("JFK");
        findItinerary2(tickets);

        return new ArrayList<>(result);
    }

    public boolean findItinerary2(List<List<String>> tickets) {
        if (result.size() == tickets.size() + 1) {
            return true;
        }

        String res = result.getLast();
        if (map.containsKey(res)) {//防止出现null
            Map<String, Integer> opt = map.get(res);
            for (Map.Entry<String, Integer> ls : opt.entrySet()) {
                int count = ls.getValue();
                if (count > 0) {
                    ls.setValue(count - 1);
                    result.add(ls.getKey());
                    if (findItinerary2(tickets)) return true;
                    ls.setValue(count);
                    result.removeLast();
                }
            }
        }


        return false;
    }
}
